package com.cet.algorithm.二叉树.二叉搜索树的最小绝对差;

import java.util.Stack;

/**
 * @program: cet-practice
 * @description: 二叉搜索树最小绝对值差
 * @author: 陈恩涛
 * @create: 2023-04-05 19:22
 **/
public class LC530 {

    static int result = Integer.MAX_VALUE;

    static TreeNode pre = null;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(0), new TreeNode(48, new TreeNode(12), new TreeNode(49)));
        System.out.println(getMinimumDifference(root));
    }

    static int getMinimumDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }
//        recurTraversal(root);
        iterateTraversal(root);
        return result;
    }

    /**
     * BST最小绝对差，递归解法
     * @param root BST root node
     */
    static void recurTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        recurTraversal(root.left);

        if (pre != null) {
            result = Math.min(result, root.val - pre.val);
        }
        pre = root;

        recurTraversal(root.right);
    }

    /**
     * BST最小绝对差，迭代解法
     * @param root  bst root node
     */
    static void iterateTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) {
            stack.push(root);
        }
        TreeNode cur = null;
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (cur != null) {
                stack.pop();
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                stack.push(cur);
                stack.push(null);
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            } else {
                stack.pop();
                cur = stack.pop();
                if (pre != null) {
                    result = Math.min(result, cur.val - pre.val);
                }
                pre = cur;
            }
        }
    }

}
